/**
 * 二次实现AVL树插入
 */
public class AVLTree {
    public static class TreeNode {
        int val;
        int bf;
        TreeNode left;
        TreeNode right;
        TreeNode parent;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    TreeNode root;
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            // 第一次插入，绑定为头结点
            root = node;
            return true;
        }

        // 不是第一次插入，按照二叉搜索树的插入，找到叶子节点
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val) {
                // cur.val < val
                parent = cur;
                cur = cur.right;
            }else {
                // cur.val == val 当前节点已存在
                return false;
            }
        }
        // cur 到叶子节点了，当前的父亲节点是parent 判断当前的cur 是插入parent的左侧还是右侧
        if(parent.val > val) {
            parent.left = node;
        }else {
            // parent.val < val
            parent.right = node;
        }
        node.parent = parent;
        cur = node;
        // 当前插入成功，接下来更新平衡因子
        while(parent != null) {
            // 更新平衡因子
            if(cur == parent.left) {
                parent.bf--;
            }else {
                parent.bf++;
            }
            if(parent.bf == 0) {
                // 表示当前 parent的节点是平衡的 无需向上判断
                break;
            }else if(parent.bf == 1 || parent.bf == -1) {
                // 当前节点的bf绝对值等于1 需要向上走继续来调整和判断平衡因子
                cur = parent;
                parent = parent.parent;
            }else {
                // 这里是不平衡了，需要进行选择
                if(parent.bf == 2) {
                    if(cur.bf == 1) {
                        rotaryLeft(parent);
                    }else {
                        rotaryRL(parent);
                    }
                }else {
                    // parent.bf == -2
                    if(cur.bf == -1) {
                        rotaryRight(parent);
                    }else {
                        rotaryLR(parent);
                    }
                }
                // 已经旋转了，就无需继续判断了
                break;
            }
        }
        return true;
    }

    /**
     * 左右双旋
     * @param parent
     */
    private void rotaryLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        int bf = subLR.bf;
        rotaryLeft(parent.left);
        rotaryRight(parent);
        if(bf == -1) {
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }

    /**
     * 右左双旋
     * @param parent
     */
    private void rotaryRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;
        rotaryRight(parent.right);
        rotaryLeft(parent);
        if (bf == 1) {
            parent.bf = -1;
            subRL.bf = 0;
            subR.bf = 0;
        } else if (bf == -1) {
            // bf == -1
            parent.bf = -1;
            subRL.bf = 0;
            subR.bf = 0;
        }
    }


    /**
     * 单右旋
     */
    private void rotaryRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;

        if(subLR != null) {
            subLR.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subL;



        if(parent == root) {
            root = subL;
            root.parent = null;
        }else {
            if(pParent.left == parent) {
                pParent.left = subL;
            }else {
                // pParent.left == parent
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        // 更新平衡因子
        subL.bf = 0;
        parent.bf = 0;

    }

    /**
     * 单左旋
     * @param parent
     */
    private void rotaryLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        subR.left = parent;
        TreeNode pParent = parent.parent;// 保留parent的父节点
        parent.parent = subR;

        parent.right = subRL;
        if(subRL != null) {// 判断，如果说subRL是null就无需绑定父节点
            subRL.parent = parent;
        }
        if(parent == root) {// parent 是根节点 直接更新subR为根节点
            root = subR;
            root.parent = null;
        }else {
            // 不是根节点 就需要判断 parent 在父节点的左边还是父节点的右边
            if(pParent.left == parent) {
                pParent.left = subR;
            }else {
                // pParent.right == parent
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        // 到这里已经旋转完毕，更细平衡因子
        parent.bf = 0;
        subR.bf = 0;
    }

    private int height(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);
        return leftH > rightH ? leftH+1 : rightH+1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }

        int leftH = height(root.left);
        int rightH = height(root.right);

        if(rightH - leftH != root.bf) {
            System.out.println("平衡因子错误" + root.val);
            return false;
        }
        return Math.abs(leftH-rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
}
